package com.celan.year2023.month02.day03;

public class Solution {
    int sum = 0;
    int x;

    public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
        sum = n;//总节点数
        this.x = x;
        int target = n / 2;
        if (x == root.val) return dfs(root.left) != dfs(root.right);

        TreeNode XFather = findX(root);
        TreeNode X = (XFather.left != null && XFather.left.val == x) ? XFather.left : XFather.right;
        //父节点的子节点数量
        int father = XFather.left.val == x ? dfs(XFather.right) + 1 : dfs(XFather.left) + 1;
        //三种方法，一种挡父节点，一种挡左节点，一种挡右节点
        //1.挡父节点，x玩家能到达的点为他所在位置的所有子节点
        int blue1 = dfs(X);
        //2.挡左子节点,右子节点+父节点的子节点
        int blue2 = dfs(X.right) + father + 1;
        //3.挡右子节点,左子节点+父节点的子节点
        int blue3 = dfs(X.left) + father + 1;
        return blue1 <= target || blue2 <= target || blue3 <= target;
    }

    private int dfs(TreeNode root) {
        if (root == null) return 0;

        int cnt = 1;
        if (root.left != null) cnt += dfs(root.left);
        if (root.right != null) cnt += dfs(root.right);
        return cnt;
    }

    //找到第一个蓝节点的父节点
    TreeNode findX(TreeNode node) {
        if (node == null) return null;
        if ((node.left != null && node.right != null) && (node.left.val == x || node.right.val == x)) return node;
        TreeNode left = findX(node.left);
        TreeNode right = findX(node.right);
        if (left != null) return left;
        if (right != null) return right;
        return null;
    }
}
